The invention relates to a method for synchronization in networks, as claimed in the precharacterizing clause of the independent patent claim.
Many applications make use of computer resources (nodes) which are distributed in networks, for example in order to improve the performance and/or the error tolerance. In some of these applications it is necessary to have a common time base for all of the connected computer resources, for example in order to coordinate different events (for example, the generation of sound at different locations in order to achieve the stereo effect). This is dependent on (more or less accurate) synchronization of the local time at the various nodes.
The nodes in this case communicate via time messages, which are transported via a communications network. In this case, the communications network which is located between two specific nodes may possibly comprise two or more different types of networks, which are connected to one another.
Messages are typically transmitted in a communications network with the aid of messages which are transported via the network. In this case, depending on the type of the network and the traffic in the network—different time delays may occur during the transportation of such messages. This variability of the time delays during transportation of messages restricts the possible synchronization of the local time at the various nodes, however.
Various methods have already been proposed for synchronization of the local time at the various nodes. The “Network Time Protocol” NTP (RFC 1305, RFC 2030) has been implemented effectively as a standard method in message networks. This method allows by means of circulating messages from one node to various reference nodes and back again that reference node which results in the best connection (shortest delay times) to be selected for updating of the node's own local clock. However, this method generally requires two or more reference nodes, and with a smaller number of time messages less accurate synchronization is also achieved.
Furthermore, so-called probabilistic synchronization methods have already been proposed, for example in “Probabilistic Clock Synchronization”, Distributed Computing, vol. 4, No. 3, pp. 146-158, 1989 (Cristian, F) and in “A Decentralized High Performance Time Service Architecture”, (Dolev, D; Reischuk, R; Strong, R; Wimmers, E), 1995. The nodes select the best of a number of time messages from a reference clock, in order to set or adapt their local time in each case. This selection of the respectively best time message from the reference clock is possible because the individual nodes repeatedly transmit circulating messages and receive them again and thus check the reference clock. On the basis of the delay time of these circulating messages, the various nodes then know which of the time messages from the reference clock are the best ones (for example those time messages from the reference clock which arrive a short time later than a circulating message with a very short circulation time).
This method has the disadvantage that the various nodes have to transmit, receive and evaluate circulating messages repeatedly in order to make it possible to assess which of the time messages from the reference clock are the best ones. These circulating messages on the one hand increase the traffic on the network, since each node to be synchronized generates its own circulating messages. Furthermore, the respective node only ever knows the total delay time of one circulating message—that is to say a message which has been transmitted by it and received again by it—and it therefore cannot state whether the message, for example, was traveling for a particularly long time on the forward path to a specific node or on the return path from this node through the network. To this extent, the synchronization accuracy is also restricted, since only the total delay time of a circulating message is ever available as a selection criterion for synchronization of the local time at the nodes. Finally—particularly when there is a large amount of traffic on the network—it is possible for the total delay time of a circulating message over a lengthy time period not to be sufficiently short and, in consequence, for it to be impossible to synchronize the local time to the reference time at the various nodes, or for such synchronization not to be particularly accurate, in this time period.
Another probabilistic method which is described by way of example in “Probabilistic Clock Synchronization in Distributed Systems” (Arvind, K.), IEEE Trans. Parallel and Distributed Systems, vol. 5, No. 5, pp. 474-487, May 1994, uses only time messages which are transported through the network in one direction, that is to say the only time messages which are transported to the various nodes are those which inform the various nodes of the reference time. No circulating messages are generated by the nodes in this case. This method has the disadvantage that all the time messages which inform the various nodes of the reference time are used by the nodes for synchronization of the local time, irrespective of whether these messages had now been en route for a comparatively long or short time in the network, and not just the best time messages, as in the case of the method described further above. No selection is therefore made of the time messages which are used for synchronization of the local time. On the other hand, this method does not place such a load on the traffic on the network. One advantage of unidirectional transmission of time messages is also that they can be sent as a “broadcast” that is to say only a single message need be sent, which is received by all the receiving nodes.
The local time can be synchronized very accurately at the various nodes by means of the “GPS (Global Positioning System)/Time Service”. GPS synchronization is very accurate, but a separate infrastructure is required for synchronization at each node, which is not only technically complex (additional equipment at each node), but is also costly. Furthermore, GPS can be used only to a very restricted extent within large buildings, as well, because the additional technical equipment can frequently in each case be fitted only on the roof, from where the signals must be distributed further within the building.